/**
 * 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
   若队列为空，pop_front 和 max_value 需要返回 -1
 */

// 双队列
// 构建一个递减的队列用来获取最大值
// 当将要入队值大于递减队列尾部的值，先将该值弹出，直到没有小于将要入队的值，再将该值入队


var MaxQueue = function() {
    this.queueA = [];
    this.queueB = [];
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
    if (this.queueA.length === 0) return -1;
    return this.queueB[0];
};

/** 
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
    this.queueA.push(value);
    while (this.queueB.length !== 0 && value > this.queueB[this.queueB.length - 1]) { // 判断
        this.queueB.pop();
    }
    this.queueB.push(value);
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
    if (this.queueA.length > 0) {
        let res = this.queueA.shift();
        if (res === this.queueB[0]) {
            this.queueB.shift()
        }
        return res;
    } else {
        return -1;
    }
}